package _662;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

import util.TreeNode;

public class S2 {
  public int widthOfBinaryTree(TreeNode root) {
    if (root == null) return 0;
    Queue<TreeNode> cur = null;
    Queue<TreeNode> next = new LinkedList<TreeNode>();
    Map<TreeNode, Double> pos = new HashMap<TreeNode, Double>();
    next.add(root);
    pos.put(root, 0.0);

    int level = 1;
    int max = 1;
    while (!next.isEmpty()) {
      ++level;
      cur = next;
      next = new LinkedList<TreeNode>();
      double leftest = Double.MAX_VALUE;
      double rightest = 0;
      while (!cur.isEmpty()) {
        TreeNode node = cur.poll();
        if (node != null) {
          double parentPos = pos.get(node);
          if (node.left != null) {
            next.add(node.left);
            double posLeft = parentPos * 2;
            pos.put(node.left, posLeft);
            if (posLeft < leftest) {
              leftest = posLeft;
            }
            if (posLeft > rightest) {
              rightest = posLeft;
            }
          }
          if (node.right != null) {
            next.add(node.right);
            double posRight = parentPos * 2 + 1;
            pos.put(node.right, posRight);
            if (posRight < leftest) {
              leftest = posRight;
            }
            if (posRight > rightest) {
              rightest = posRight;
            }
          }
        }
      }
      int width = (int)(rightest - leftest) + 1;
      if (width > max) {
        max = width;
      }
    }

    return max;
  }

private static void test(String[] nums) {
  S2 s = new S2();
  TreeNode tree = TreeNode.constructTree(nums);
  TreeNode.printTree(tree);
  System.out.println("width: " + s.widthOfBinaryTree(tree) + "\n-----------------------------");
}

  public static void main(String[] args) {
    // Test 1
    String[] t1 = {"1", "3", "2", "5", "3", "null", "9"};
    test(t1);

    // Test 2
    String[] t2 = {"1", "3", "null", "5", "3"};
    test(t2);

    // Test 3
    String[] t3 = {"1", "3", "2", "5"};
    test(t3);

    // Test 4
    String[] t4 = {"1", "3", "2", "5", "null", "null", "9", "6", "null", "null", "7"};
    test(t4);

    // Test 5
    String[] t5 = {"0", "null", "0", "null", "0", "null", "0", "null", "0", "0" };
    test(t5);

    String[] t6 = {"0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","0"};
    test(t6);
  }
}